package com.echo.boot.structure.tree.binarytree;

import com.echo.boot.structure.tree.printer.BinaryTreeInfo;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 *
 * @author CQ
 * Date: 2020/5/9
 * Time: 17:28
 */
public class BinaryTree<E> implements BinaryTreeInfo {

    /**
     * 元素数量
     */
    protected int size;
    /**
     * 根节点
     */
    protected Node<E> root;

    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        // 判断自己是不是左子树
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        // 判断自己是不是右子树
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        // 返回父节点的兄弟节点

        public Node<E> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }

    }

    /**
     * 元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空所有的元素
     */
    public void clear() {
        root = null;
        size = 0;
    }

    protected Node<E> createNode(E element, Node<E> parent) {
        return new Node<>(element, parent);
    }

    // 所有二叉树遍历

    /**
     * @author CQ
     * @DESCRIPTION: 前序遍历; 前序遍历的作用 : 树状结构展示(注意左右子树的顺序);
     * @DESCRIPTION: 前序遍历:先根节点, 左子树, 最后右子树;
     * @params: 策略模式： 提供外部访问树的元素
     * @return:
     * @Date: 2020/5/18 7:35
     * @Modified By:
     */
    public void preloaderTraversal(Visitor<E> visitor) {
        if (checkVisitor(visitor)) {
            return;
        }
        preloaderTraversal(root, visitor);
    }


    private void preloaderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        preloaderTraversal(node.left, visitor);
        preloaderTraversal(node.right, visitor);
    }

    /**
     * @author CQ
     * @DESCRIPTION: 中序遍历 （二叉搜索树的中序遍历是升序或降序）
     * @DESCRIPTION: 中序遍历 : 先左子树,根节点,后右子树.
     * @params: [visitor] 提供外部访问树的元素
     * @return: void
     * @Date: 2020/5/18 7:39
     * @Modified By:
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorderTraversal(root, visitor);
    }

    public void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        if (visitor.stop) {
            return;
        }
        inorderTraversal(node.left, visitor);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);
    }

    /**
     * @author CQ
     * @DESCRIPTION: 后序遍历, 先左子节点, 右节点, 最后根节点.
     * @params: [visitor]
     * @return: void
     * @Date: 2020/5/18 7:42
     * @Modified By:
     */
    public void postOrderTraversal(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        postOrderTraversal(root, visitor);
    }

    private void postOrderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        if (visitor.stop) {
            return;
        }
        postOrderTraversal(node.left, visitor);
        postOrderTraversal(node.right, visitor);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * @author CQ
     * @DESCRIPTION: 层级遍历
     * @params: [visitor]
     * @return: void
     * @Date: 2020/5/18 7:46
     * @Modified By:
     */
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        levelOrderTraversal(root, visitor);
    }

    private void levelOrderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        LinkedList<Node<E>> deque = new LinkedList<>();
        deque.offer(node);
        while (!deque.isEmpty()) {
            Node<E> eNode = deque.poll();
            if (visitor.visit(eNode.element)) {
                return;
            }
            if (eNode.left != null) {
                deque.offer(eNode.left);
            }
            if (eNode.right != null) {
                deque.offer(eNode.right);
            }
        }
    }

    /**
     * @author CQ
     * @DESCRIPTION: 判断是否为完全二叉树(叶子节点只会出现最后2层, 且最后 1 层的叶子节点都靠左对齐);
     * @params: []
     * @return: boolean
     * @Date: 2020/5/18 9:59
     * @Modified By:
     */
    public boolean isComplete() {
        return isComplete(root);
    }

    /**
     * 如果树为空,返回false;
     * 如果树不为空
     * 1.node.left != null && node.right != null,将node.left,node.right入队;
     * 2.node.left  == null && node.right != null,返回 false;
     * 3.node.left != null && node.right == null 或者 node.left == null && node.right == null
     * 那么后面遍历的节点应该都是叶子节点,才是完全二叉树
     * 否者返回 false;
     */
    private boolean isComplete(Node<E> node) {
        if (node == null) {
            return false;
        }
        LinkedList<Node<E>> deque = new LinkedList<>();
        deque.offer(node);
        boolean leaf = false;
        while (!deque.isEmpty()) {
            Node<E> eNode = deque.poll();
            if (leaf && !node.isLeaf()) {
                return false;
            }
            if (node.left != null) {
                deque.offer(node.left);
            } else if (node.right != null) {
                return false;
            }
            if (node.right != null) {
                deque.offer(node.right);
            } else {
                leaf = true;
            }
        }
        return true;
    }

    /**
     * @author CQ
     * @DESCRIPTION: 返回前驱结点(中序遍历的前一个节点)
     * @params: []
     * @return: 前序节点
     * @Date: 2020/5/18 15:50
     * @Modified By:
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) {
            return null;
        }
        // 前驱节点在左子树中(left.right.right.right....)
        if (node.left != null) {
            // 左子树不为空,则找到它的最右节点
            Node<E> p = node.left;
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 能来到这里说明左子树为空
        // 跳出循环条件
        // 当父节点不为空，则顺着父节点找，直到找到【某结点为父节点的右子节点】时
        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }
        // 来到这里有以下两种情况：
        // node.parent == null	无前驱，说明是根结点
        // node.parent.right == node 找到【某结点为父节点的右子节点】
        return node.parent;
    }

    /**
     * @author CQ
     * @DESCRIPTION: 返回后驱结点(中序遍历的后一个节点)
     * @params: []
     * @return: 后序节点
     * @Date: 2020/5/18 15:50
     * @Modified By:
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            Node<E> p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        // 来到这里说明没有右节点
        // 跳出循环条件
        // 当父节点不为空，则顺着父节点找，直到找到【某结点为父节点的左子节点】时
        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }
        // 来到这里有以下两种情况：
        // node.parent == null   无后驱，说明是根结点
        // node.parent.left == node  找到【某结点为父节点的左子节点】
        return node.parent;

    }

    /**
     * @author CQ
     * @DESCRIPTION: 树的深度(高度)
     * @params: []
     * @return: int
     * @Date: 2020/5/21 8:38
     * @Modified By:
     */
    public int height() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        int i = height(node.left);
        int j = height(node.right);
        int max = Math.max(i, j);
        return 1 + max;
//        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * @author CQ
     * @DESCRIPTION: 输的深度(高度)
     * @params: []
     * @return: int
     * @Date: 2020/5/21 8:38
     * @Modified By:
     */
    public int treeHeight() {
        return treeHeight(root);
    }

    private int treeHeight(Node<E> node) {
        if (node == null) {
            return 0;
        }
        LinkedList<Node<E>> deque = new LinkedList<>();
        deque.offer(node);
        int height = 0;
        int levelSize = 1;
        while (!deque.isEmpty()) {
            Node<E> eNode = deque.poll();
            levelSize--;
            if (eNode.left != null) {
                deque.offer(eNode.left);
            }
            if (eNode.right != null) {
                deque.offer(eNode.right);
            }
            if (levelSize == 0) {
                levelSize = deque.size();
                height++;
            }
        }
        return height;
    }

    private boolean checkVisitor(Visitor<E> visitor) {
        if (visitor == null) {
            return true;
        }
        return false;
    }


    //打印二叉树开始
    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }
    //打印二叉树结束


}
